import java.util.Arrays;

public class Solution1314 {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int[][] sum=new int[mat.length+1][mat[0].length+1];
        for (int i=0;i<mat.length;i++){
            for (int j=0;j<mat[0].length;j++){
                sum[i+1][j+1]=sum[i+1][j]+sum[i][j+1]+mat[i][j]-sum[i][j];
            }
        }
        int[][] ans=new int[mat.length][mat[0].length];
        for (int i=0;i<mat.length;i++){
            for (int j=0;j<mat[0].length;j++){
                int a=Math.min(i+k,mat.length-1),b=Math.min(j+k,mat[0].length-1),
                        c=Math.max(i-k,0),d=Math.max(j-k,0);
                ans[i][j]=sum[a+1][b+1]-sum[c][b+1]-sum[a+1][d]+sum[c][d];
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.deepToString(new Solution1314().matrixBlockSum(new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}, 1)));
    }
}
